package newcoder_exp.bytedance;

import java.util.*;

import org.junit.Test;

public class BD12 {

    
    @Test
    public void test() {
        int[] nums = new int[]{1,2,3,5,1};
        System.out.println(maxNum(nums, 2));
        System.out.println(maxNum1(nums, 2));
        System.out.println(maxNum2(nums, 2));
    }


    public long maxNum2(int[] nums, int k) {
        int len;
        if (nums == null || (len = nums.length) == 0 || len < k) return -1;
        long[][] f = new long[len + 1][k + 1];

        //f[0][i] = 0 表示一个都没选
        for (int i = 1; i <= len; i++) {
            // f[i][0] = f[i - 1][0];
            for (int j = 0; j < k; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[i - 1][j + 1] * 10 + nums[i - 1]);
            }
            f[i][k] = f[i - 1][k];
        }
        return f[len][0];
    }
    //数组中k个元素组成的最大整数

      /* 
        变化量：idx, k
        边界值：
            f[len][i] = cur? idx == len => 
            f[i][k] = cur?
    */
    public long maxNum(int[] nums, int k) {
        int len;
        if (nums == null || (len = nums.length) == 0 || len < k) return -1;
        long[][] f = new long[len + 1][k + 1];
        //f[len][j]恒为0 ： f[len, len-1]区间不存在
        for (int i = len - 1; i >= 0; i--) {
            f[i][0] = f[i + 1][0];
            for (int j = 1; j <= k; j++) {
                f[i][j] = Math.max(f[i + 1][j], nums[len - 1 - i] + f[i + 1][j - 1] * 10);
            }
        }
        return f[0][k];
    }

  
    long[][] p;

    public long maxNum1(int[] nums, int k) {
        p = new long[nums.length + 1][k + 1];
        for (int i = 0; i <= nums.length; i++) {
            Arrays.fill(p[i], -1);
        }
        return dfs(nums, 0, 0, k);
    }

    int id = 0;
    public long dfs(int[] nums, int idx, long cur, int k) {

        if (idx == nums.length || k == 0) {
            p[idx][k] = cur;
            return cur;
        }

        // if (p[idx][k] != -1) {
        //     System.out.println("命中" + (id++));
        //     return p[idx][k];
        // }
        long res1 = 0;

        res1 = dfs(nums, idx + 1, cur * 10 + nums[idx], k - 1);
        long res2 = dfs(nums, idx + 1, cur, k);
        p[idx][k] = Math.max(res1, res2);
        return p[idx][k];
    }


    //九宫格解法
    public List<List<String>> countNine() {
        res = new ArrayList<>();
        // visited = new boolean[3][3][4];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                dfs(new ArrayList<>(), i, j, 4);
            }
        }
        return res;
    }
    boolean[][] flag = new boolean[3][3];
    List<List<String>> res;
    Set<String> set = new HashSet<>();
    public void dfs(List<int[]> cur, int i, int j, int count) {
        if (!isInArea(i, j) || flag[i][j]) return;
        if (count == 0) {
            List<String> list = new ArrayList<>();
            char[][] t = new char[3][3];
            for (int k = 0; k < 3; k++) {
                Arrays.fill(t[k], '·');
            }
            for (int k = 0; k < cur.size(); k++) {
                int[] tmp = cur.get(k);
                t[tmp[0]][tmp[1]] = 'o';
            }
            String s = "";
            for (int k = 0; k < 3; k++) {
                list.add(new String(t[k]));
                s += new String(t[k]);
            }
            if (!set.contains(s)) {
                set.add(s);
                res.add(list);
            }
            return;
        }
        flag[i][j] = true;
        cur.add(new int[]{i, j});
        dfs(cur, i + 1, j, count - 1);//下
        dfs(cur, i - 1, j, count - 1);//上
        dfs(cur, i, j + 1, count - 1);//右
        dfs(cur, i, j - 1, count - 1);//左
        dfs(cur, i + 1, j - 1, count - 1);//左下
        dfs(cur, i + 1, j + 1, count - 1);//右下
        dfs(cur, i - 1, j + 1, count - 1);//右上
        dfs(cur, i - 1, j - 1, count - 1);//左上
        cur.remove(cur.size() - 1);
        flag[i][j] = false;
    }

    public boolean isInArea(int i, int j) {
        return i >= 0 && i < 3 && j >= 0 && j < 3;
    }

    @Test
    public void test1() {
        System.out.println(countNine());     
    }
}
